Search results for "General Routing Problem"

showing 6 items of 6 documents

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

2006

[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.

Arc routingGeneral Computer ScienceLinear programmingMixed Chinese postman problemMixed graphMixed rural postman problemManagement Science and Operations ResearchRoute inspection problemTree traversalModeling and SimulationEnhanced Data Rates for GSM EvolutionRouting (electronic design automation)Mixed general routing problemMATEMATICA APLICADAAlgorithmArc routingMathematicsVariable (mathematics)
researchProduct

The mixed capacitated general routing problem with turn penalties

2011

In this paper we deal with the mixed capacitated general routing problem with turn penalties. This problem generalizes many important arc and node routing problems, and it takes into account turn penalties and forbidden turns, which are crucial in many real-life applications, such as mail delivery, waste collection and street maintenance operations. Through a polynomial transformation of the considered problem into a Generalized Vehicle routing problem, we suggest a new approach for solving this new problem by transforming it into an Asymmetric Capacitated Vehicle routing problem. In this way, we can solve the new problem both optimally and heuristically using existing algorithms. A powerfu…

Capacitated vehicle routing problemMathematical optimizationRouting problemsPolynomial transformationReal-life applicationsTurn penaltiesCapacitated general routing problemRouting algorithmsVehicle Routing ProblemsTransformationPolynomial transformationsArtificial IntelligenceVehicle routing problemDestination-Sequenced Distance Vector routingGeneral routing problemMathematicsta113Average deviationStatic routingWaste collectionNode (networking)General EngineeringSolution methodsMaintenance operationsVehicle routingComputer Science ApplicationsMemetic algorithmsBenchmark (computing)Network routingMemetic algorithmRouting (electronic design automation)MATEMATICA APLICADAAlgorithmsExpert Systems with Applications
researchProduct

The mixed general routing polyhedron

2003

[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…

Discrete mathematicsGeneral MathematicsArc RoutingMixed graphFacetsPolyhedral combinatoricsRural Postman Problemlaw.inventionGeneral Routing ProblemCombinatoricsTree traversalMixed Chinese Postman ProblemlawroutingGraph traversalGraph (abstract data type)Destination-Sequenced Distance Vector routingMATEMATICA APLICADACircle graphArc routingSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsPolyhedral graph
researchProduct

The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra

1998

[EN] In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron, We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-i…

Facet (geometry)Information Systems and ManagementGeneral Computer ScienceGeneralizationHoneycomb (geometry)Facets of polyhedraGraph theoryManagement Science and Operations ResearchTravelling salesman problemIndustrial and Manufacturing EngineeringRural Postman ProblemGeneral Routing ProblemCombinatoricsPolyhedronModeling and SimulationGraphical Traveling Salesman ProblemCombinatorial optimizationMathematics::Metric GeometryRouting (electronic design automation)MATEMATICA APLICADAMathematicsRouting
researchProduct

The stacker crane problem and the directed general routing problem

2015

[EN] This article deals with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP contains a large number of important arc and node routing problems as special cases, including the SCP. Large families of facet-defining inequalities for the DGRP are described and a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included.

Mathematical optimizationDirected general routing problemStacker crane problemComputer Networks and CommunicationsStackerNode (networking)Branch-and-cut algorithmDirected graphResolution (logic)Directed rural postman problemHardware and ArchitectureRouting (electronic design automation)MATEMATICA APLICADASoftwareInformation SystemsMathematics
researchProduct

New Results on the Mixed General Routing Problem

2005

[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …

Mathematical optimizationmedicine.medical_specialtyBranch and boundPolyhedral combinatoricsMixed graphHoneycomb (geometry)Mixed rural postman problemManagement Science and Operations ResearchPolyhedral combinatoricsComputer Science ApplicationsRural postman problemVehicle routing problemmedicineDestination-Sequenced Distance Vector routingRouting (electronic design automation)General routing problemMATEMATICA APLICADACutting-plane methodMathematics
researchProduct